<?php
include_once "init.php";
include_once "func/print.php";
/**
 * 斐波那契数
 * 1 2 3 5 8 13
 */

/**
 * 计算斐波那契数的递归算法
 * @param int $n 位数
 */
function fibonacci($n)
{
    if($n <= 1){
        return 1;
    }
    return fibonacci($n-1) + fibonacci($n-2);
}

/**
 * 计算斐波那契数的动态规划算法
 * @param int $n 位数
 */
function fibonacci_d($n)
{
    if($n <= 1){
        return 1;
    }
    $before_1=1;
    $before_2=1;
    for($i=2; $i<=$n; $i++){
        $fib=$before_1+$before_2;
        $before_2=$before_1;
        $before_1=$fib;
    }
    return $fib;
}

/**
 * 计算斐波那契数列的动态规划算法
 * @param int $n 位数
 */
function fibonacci_sequence_d($n)
{
    if($n < 0){
        return [];
    }
    if($n === 1){
        return [1];
    }
    $list=[1,2];
    if($n === 2){
        return $list;
    }
    /**从 $n===3 开始计算，$i=当前位数 */
    for($i=3; $i<=$n; $i++){
        $list[]=$list[$i-3]+$list[$i-2];
    }
    return $list;
}

echo fibonacci(10)."\r\n";
echo fibonacci_d(10)."\r\n";
print_list(fibonacci_sequence_d(100));
